1. Field of the Invention
This invention relates to a cryptographic key recovery system and, more particularly, to a key recovery system that is interoperable with existing systems for establishing keys between communicating parties.
2. Description of the Related Art
Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption operation on a plaintext input block, using an encryption key, to produce a ciphertext output block. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the plaintext block.
Encryption systems fall into two general categories. Symmetric (or private key) encryption systems such as the Data Encryption Standard (DES) system use the same secret key for both encrypting and decrypting messages. In the DES system, a key having 56 independently specifiable bits is used to convert 64-bit plaintext blocks to ciphertext blocks, or vice versa.
Asymmetric (or public key) encryption systems, on the other hand, use different keys that are not feasibly derivable from one another for encryption and decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver's public key. Only the receiver may decrypt the message, however, since only he has the private key. Perhaps the best-known asymmetric encryption system is the RSA encryption system, named after its originators Rivest, Shamir and Adleman.
Asymmetric encryption systems are generally more computationally intensive than symmetric encryption systems, but have the advantage that they do not require a secure channel for the transmission of encryption keys. For this reason, asymmetric encryption systems are often used for the one-time transport of highly sensitive data such as symmetric encryption keys.
Data encryption systems of all types have attracted the attention of government intelligence agencies and law enforcement agencies, since the same cryptographic strength that prevents decryption by unauthorized third parties also prevents decryption by intelligence or law enforcement officials having a legitimate reason for wanting to access the plaintext data. Because of such concerns, governments have either prohibited the use or export of strong encryption systems or have conditioned their approval on the use of weakened keys that are susceptible to key-exhaustion attacks (i.e., systematically testing all possible keys until the right one is found). Such weak encryption systems have the obvious disadvantage that they are just as vulnerable to unauthorized third parties as they are to authorized government officials.
Various cryptographic key recovery systems have recently been proposed as a compromise between the demands of communicating parties for privacy in electronic communications and the demands of law enforcement agencies for access to such communications when necessary to uncover crimes or threats to national security. Generally, in such key recovery systems, all or part of the key used by the communicating parties is made available to one or more key recovery agents, either by actually giving the key portions to the key recovery agents (in which case the key portions are said to be "escrowed") or by providing sufficient information in the communication itself (as by encrypting the key portions) to allow the key recovery agents to regenerate the key portions. Key recovery agents would reveal the escrowed or regenerated key portions to a requesting law enforcement agent only upon presentation of proper evidence of authority, such as a court order authorizing the interception. The use of multiple key recovery agents, all of which must cooperate to recover the key, minimizes the possibility that a law enforcement agent can improperly recover a key by using a corrupt key recovery agent.
Key recovery systems serve the communicants' interest in privacy, since their encryption system retains its full strength against third parties and does not have to be weakened to comply with domestic restrictions on encryption or to meet export requirements. At the same, key recovery systems serve the legitimate needs of law enforcement by permitting the interception of encrypted communications in circumstances where unencrypted communications have previously been intercepted (as where a court order has been obtained).
In addition to serving the needs of law enforcement, key recovery systems find application in purely private contexts. Thus, organizations may be concerned about employees using strong encryption of crucial files where keys are not recoverable. Loss of keys may result in loss of important stored data.
A number of desirable features of a key recovery system have been identified. Thus, considering first higher-priority features, a key recovery system should be capable of being implemented in software or hardware. It should not require communication with a third party for installation (i.e., it should work "out of the box"), nor should it require communication with a third party during message creation or connection setup. It should provide interoperability between users in different countries. The algorithms used should be publicly known, and the mechanism should be algorithm independent. The design should be open and should be capable of being implemented by multiple vendors based on published specifications. It should provide a key recovery capability independently for each country. It should provide, in a single system, the flexibility for different levels of security in different environments, and provide the highest level of cryptographic security allowable by law. It should be a modular extension (add-on) to existing cryptographic systems. It should permit any key exchange mechanism to be used, while optionally retaining a control point that enforces compliance with key recovery. The security properties of the exchanged key should be maintained, except for allowing for recovery.
Other features, though of lesser priority, are nevertheless highly desirable. A key recovery system should support both store-and-forward (i.e, non-interactive) and interactive environments. It should support the policy option of requiring the collaboration of multiple key recovery agents to recover the key (to provide protection against a corrupt key recovery agent). It should optionally prevent a patched (rogue) implementation from interoperating with an unpatched (complying) implementation.
Key recovery systems of various types are described in D. E. Denning and D. K. Branstad, "A Taxonomy for Key Escrow Encryption Systems", Communications of the ACM, vol. 39, no. 3, Mar. 1996, pp. 34-40, incorporated herein by reference.
Several specific key recovery systems are noted below.
Micali et al. U.S. Pat. No. 5,276,737 ("Micali I") and U.S. Pat. No. 5,315,658 ("Micali II") describe a "fair" public key cryptosystem in which the private key of a public/private key pair is broken into "shares" that are given to "trustees". The "breaking" is done in such a manner that: (1) the shares of all trustees (or a predetermined quorum) are required to reconstruct the key; and (2) each trustee can individually verify the correctness of his share. When all the trustees have certified the correctness of their share, the user's public key (corresponding to the escrowed private key) is certified by a key management center. Upon a predetermined request, the trustees provide their shares to a law enforcement agent or other recovering entity, who then reconstructs the private key from the shares and, with the private key, is able to monitor communications to the user.
While the Micali system advantageously "splits" the key among a plurality of escrow agents, the system has several drawbacks. The Micali system requires the active participation of the trustees before communications can begin between the user and another party. Also, since the trustees must actually hold the shares being escrowed (or store them externally in encrypted form), each trustee may end up holding or storing a large number of shares of keys that are never the subject of a recovery request.
The copending application of D. B. Johnson et al., Ser. No. 08/629,815, filed Apr. 10, 1996, entitled "Cryptographic Key Recovery System" ("Johnson et al. I"), describes a partial key recovery system using multiple key recovery agents. In one version of the system described in that application, the sender generates a set of key recovery values (or key parts) P, Q and (optionally) R. The session key is created by combining the P and Q values by XOR addition, concatenating the result with R, and hashing the concatenation result to generate the key. The P and Q values are then encrypted using the public keys of the respective key recovery agents and the encrypted P and Q values included (along with other recovery information) in a session header accompanying the encrypted message. The R value, if generated, is not made available to any key recovery agent, but is kept secret to provide a nontrivial work factor for law enforcement agents seeking to recover the key.
The receiver verifies the correctness of the recovery information by regenerating the information using its own data and comparing the results. If the regenerated recovery information matches that in the session header, the receiver proceeds to decrypt the encrypted message.
A party (such as law enforcement) intercepting an encrypted message obtains the encrypted P and Q values and other recovery information from the accompanying session header. To recover the session key, the party presents the encrypted P and Q values from the session header to the key recovery agents, who decrypt the P and Q values and return the decrypted values to the party requesting recovery. That party then reconstructs the session key (generating the R value by brute force if necessary) and decrypts the encrypted message.
In another key recovery system, described in U.S. Pat. No. 5,557,346 to Lipner et al., the sender splits a session key into first and second session key portions by setting the first session key portion equal to a random number and setting the second session key portion equal to the XOR product of the random number and the session key. The sender creates a law enforcement access field (LEAF) by encrypting the respective session key portions with the public encryption keys of first and second key recovery agents and concatenating the two encryption products. The sender also creates a LEAF verification string (LVS) by concatenating the original session key portions and encrypts this using the session key to form an encrypted LEAF verification string (ELVS). Finally, the sender transmits an encrypted message, together with the LEAF and ELVS, to the receiver.
Before decrypting the encrypted message, the receiver regenerates the LEAF to verify that the sender has created a proper LEAF that would actually permit recovery of the session key through the key recovery agents. This is done by decrypting the ELVS to obtain the session key portions and then encrypting the respective session key portions with the public encryption keys of first and second key recovery agents. If the receiver succeeds in regenerating the transmitted LEAF in this manner, it concludes that the LEAF is genuine and proceeds to decrypt the message. Otherwise, it concludes that the LEAF is corrupt and does not proceed with the decryption step.
The copending application of D. B. Johnson et al., Ser. No. 08/681,679, filed Jul. 29, 1996, entitled "Interoperable Cryptographic Key Recovery System" ("Johnson et al. II") now U.S. Pat. No. 5,796,830, describes a key recovery system that uses an "entropy-preserving" procedure to generate key recovery values. As disclosed in the Johnson et al. II application, P, Q and R key recovery values (where P and Q are presented in encrypted form to respective key recovery agents and R is kept secret as in Johnson et al. I) are generated using a key inversion function having as inputs only the session key K being recovered and nonsecret information available to the receiver and parties assisting in the recovery process. By using such an entropy-preserving key inversion function, one avoids the necessity of having to convey additional secret information to the receiver merely to enable the receiver to verify the recovery information.
In contrast to the Micali system, the systems of Johnson et al. I and II and Lipner et al. do not require the involvement of the key recovery agents until a key is actually being recovered. However, both of the Johnson et al. systems as well as the Lipner et al. system require the encryption of new key recovery values with the public keys of the key recovery agents for each new session key. Public key encryption is a computationally expensive operation; performing this operation for each new session key greatly increases the computational overhead of the key recovery system.